package leetcode.tree;

import leetcode.tree.common.TreeNode;

import java.util.ArrayList;
import java.util.List;


/**
 * AC
 */
class Solution94 {
    public List<Integer> inorderTraversal(TreeNode root) {

        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }

        traverse(result, root);

        return result;

    }

    public void traverse(List<Integer> list, TreeNode root) {

        // 当当前二叉树的根节点为null，到达递归边界，返回
        if (root == null) {
            return;
        }

        // 遍历左子树
        traverse(list, root.left);
        // 添加当前节点
        list.add(root.val);
        // 遍历右子树
        traverse(list, root.right);

    }
}

/**
 * 94. 二叉树的中序遍历
 */
public class leetcode94 {
    public static void main(String[] args) {

        Solution94 solution94 = new Solution94();
        List<Integer> inorderTraversal = solution94.inorderTraversal(generateDate());
        System.out.println(inorderTraversal);

    }

    private static TreeNode generateDate() {
        TreeNode root = new TreeNode(1);
        root.right = new TreeNode(2);
        root.right.left = new TreeNode(3);
        return root;
    }
}
